package com.hardy.data_structure;

import java.util.Arrays;

/**
 * Author: Hardy
 * Date:   2020/7/5
 * Description:
 **/
public class SortFast {
    // {1, 2, 6, 3, 8, 0, 3}


    public static void main(String[] args) {
        int[] a = {1, 2, 6, 3, 8, 0, 3};

        sort1(a);

        System.out.println(Arrays.toString(a));
    }

    private static void sort(int[] a) {
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int b, int e) {
        // 取最大值
        int part = a[e];

        int i = b;
        int j = e;

        while (i < j) {
            // 左边 比分割值小 右移
            while (i < j && a[i] < part) i++;
            // 右边 比分割值大 左移
            while (i < j && a[j] > part) j--;

            // 左 = 右 = part
            if (i < j && a[i] == a[j]) {
                j--;
            } else {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }

        if (b <= i - 1) sort(a, b, i - 1);
        if (i + 1 <= e) sort(a, i + 1, e);
    }


    private static void sort1(int[] a) {
        sort1(a, 0, a.length - 1);
    }

    private static void sort1(int[] a, int b, int e) {
        if (b >= e) return;

        // 取最大值
        int temp = a[b];

        int i = b;
        int j = e;

        // 4 3 6 1 6 2 8
        while (i < j) {
            while (i < j && a[i] <= temp) i++;
            while (i < j && a[j] > temp) j--;

            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        a[b] = a[i];
        a[i] = temp;

        sort1(a, b, i - 1);
        sort1(a, i + 1, e);
    }
}
